package com.bo.day20231205;

import java.util.*;

/**
 * 加强堆(泛型一定是非基础类型的,因为使用hashMap使用基础类型会覆盖,基础类型用的值传递)
 * 如果使用基础类型需要一个包装类
 * 反向索引
 *
 * @Author: gpb
 * @Date: 2023/12/6 16:38
 * @Description:
 */
public class HeapGreater<T> {

    /**
     * 堆
     */
    private List<T> heap;
    /**
     * 堆的反向索引
     */
    private Map<T, Integer> indexMap;

    /**
     * 堆大小
     */
    private int heapSize;

    /**
     * 比较器
     * 返回值>0：o1排在前面,o2排在后面
     * 返回值=0：说明o1和o2比较的值一样
     * 返回值<0：o2排在前面,o1排在后面
     */
    private Comparator<? super T> comp;

    public HeapGreater (Comparator<? super T> c) {
        this.heap = new ArrayList<>();
        this.indexMap = new HashMap<>();
        this.heapSize = 0;
        comp = c;
    }

    public boolean isEmpty () {
        return heapSize == 0;
    }

    public int size () {
        return heapSize;
    }

    public T peek () {
        return heap.get(0);
    }

    public boolean contains (T data) {
        return indexMap.containsKey(data);
    }


    public void push (T data) {
        // 添加
        heap.add(data);
        // 记录数组的索引位置,反向表
        indexMap.put(data, heapSize);
        heapInsert(heapSize++);
    }

    public T pop () {
        T t = heap.get(0);
        // 0位置的数和最后一个数进行交换
        swap(0, --heapSize);
        // 堆和反向索引都要删除改元素
        heap.remove(t);
        indexMap.remove(t);
        // 0位置的数组要下沉
        heapIfy(0);
        return t;
    }

    /**
     * 删除元素
     *
     * @param data
     */
    public void remove (T data) {
        // 删除元素的索引位置
        Integer dataIndex = indexMap.get(data);
        // 最后一个元素
        T t = heap.get(heapSize - 1);
        // 删除元素
        indexMap.remove(data);
        heap.remove(--heapSize);
        if (dataIndex != heapSize) {
            // 删除元素位置要和最后一个元素交换位置
            heap.set(dataIndex,t);
            indexMap.put(t,dataIndex);
            // 调整堆
            resign(t);
        }
    }

    // 请返回堆上的所有元素
    public List<T> getAllElements () {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    public void heapInsert (int index) {
        // 这里要使用比较器进行比较
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void heapIfy (int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int max = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
            max = comp.compare(heap.get(max), heap.get(index)) < 0 ? max : index;
            if (max == index) {
                return;
            }
            // 交换位置,继续下沉
            swap(max, index);
            index = max;
            left = index * 2 + 1;
        }
    }

    /**
     * 调整堆
     *
     * @param data
     */
    public void resign (T data) {
        Integer index = indexMap.get(data);
        // 要么上升,要么下沉,只会执行一个
        heapInsert(index);
        heapIfy(index);
    }

    private void swap (int i, int j) {
        // i,j的位置数据呼唤
        T tI = heap.get(i);
        T tJ = heap.get(j);
        heap.set(j, tI);
        heap.set(i, tJ);
        // 记录反向索引
        indexMap.put(tI, j);
        indexMap.put(tJ, i);
    }

}
